// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-11 20:58
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import org.junit.jupiter.api.Test;

public class IsSubsequence {
    /**
     * 判断s是否是t的字串
     */
    public boolean isSubsequence(String s, String t) {
        // 朴素比较 -> 时间复杂度为O(n)
        int n = s.length(), m = t.length();
        if (n == 0) {
            return true;
        }
        boolean flag = n <= m;
        if (flag) {
            return isSub(t, s, m, n);
        } else {
            return false;
        }
    }

    /**
     * s串长于t串
     */
    private boolean isSub(String s, String t, int n, int m) {
        int k = 0;
        char c = t.charAt(k);
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == c) {
                ++k;
                if (k >= m) {
                    return true;
                }
                c = t.charAt(k);

            }
        }
        return false;
    }


    @Test
    public void shout() {
        //String s = "acb";
        String s = "abc";
        String t = "ahbgdc";
        System.out.println(isSubsequence(s, t));

    }


}
